// 合并排序

#include <iostream>
#include <algorithm>
#include <cstring>

// 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48
// 3, 44, 38, 5, 47, 15, 36, 26 | 27, 2, 46, 4, 19, 50, 48
// 3, 44, 38, 5 | 47, 15, 36, 26 | 27, 2, 46, 4 | 19, 50, 48
// 3, 44 | 38, 5 | 47, 15, | 36, 26 | 27, 2 | 46, 4 | 19, 50 | 48
// 3 | 44 | 38 | 5 | 47 | 15 | 36 | 26 | 27 | 2 | 46 | 4 | 19 | 50 | 48

void _mergeSort(int arr[], int left, int right, int result[])
{
    if(left >= right) return;
    int mid = (left + right) / 2;
    _mergeSort(arr, left, mid, result);
    _mergeSort(arr, mid + 1, right, result);

    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(arr[begin1] <= arr[begin2]) result[index++] = arr[begin1++];
        else result[index++] = arr[begin2++];
    }
    while(begin1 <= end1) result[index++] = arr[begin1++];
    while(begin2 <= end2) result[index++] = arr[begin2++];
    memcpy(arr + left, result + left, sizeof(int) * (right - left + 1));
}

void mergeSort(int arr[], int n)
{
    int* result = (int*)malloc(sizeof(int) * n);
    if(result == NULL)
    {
        perror("malloc failed!");
        exit(-1);
    }

    _mergeSort(arr, 0, n - 1, result);
    free(result);
    result = NULL;
}


// 非递归
void NoRecursionMergeSort(int* arr, int size)
{	
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
	{
		perror("NoRecursionMergeSort: tmp is malloc failed!\n");
		exit(-1);
	}

	//每组的数据个数
	int groupSize = 1;

	while (groupSize < size)
	{
		//控制每一层
		for (int i = 0; i < size; i += 2 * groupSize)
		{
			//控制每组
			int begin1 = i, end1 = i + groupSize - 1;
			int begin2 = i + groupSize, end2 = i + 2 * groupSize - 1;
			printf("[%d,%d],[%d,%d]\n", begin1, end1, begin2, end2);

			//begin1不会越界，end1、begin2、end2都可能越界
			//1.end1,begin2,end2都越界
			if (end1 >= size) break;
			//2.begin2，end2越界
			else if (begin2 >= size) break;
			//3.end2越界
			else if (end2 >= size) end2 = size - 1;

			//对两组合并操作
			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2]) tmp[index++] = arr[begin1++];
				else tmp[index++] = arr[begin2++];
			}
			while (begin1 <= end1) tmp[index++] = arr[begin1++];
			while (begin2 <= end2) tmp[index++] = arr[begin2++];
			//每组拷贝
			memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}

		//每组个数翻倍
		groupSize *= 2;
	}

	free(tmp);
	tmp = NULL;
}

